/*
Copyright (c) 2009 Gary Knowles

Permission is hereby granted, free of charge, to any person
obtaining a copy of this software and associated documentation
files (the "Software"), to deal in the Software without
restriction, including without limitation the rights to use,
copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the
Software is furnished to do so, subject to the following
conditions:

The above copyright notice and this permission notice shall be
included in all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
OTHER DEALINGS IN THE SOFTWARE.
*/
#include "Luthor.h"

using namespace std;
using namespace LuaWanbHash;
namespace LuaWanbHash {
#define OP LT::op()
#define CL cl()
#define MV ltMV
static Tbl et=OP.CL;

static Var vnn=MV("nn"),vstart=MV("start"),vend=MV("end"),vstarttag=MV("starttag"),vendtag=MV("endtag"),
           vmachnum=MV("mach#"),vstartbacktrace=MV("startbacktrace"),vbts=MV("bts"),vnext=MV("next"),
           veplist=MV("eplist"),vemit=MV("emit"),vbacktrace=MV("backtrace"),vxor=MV("xor"),
           vmatch=MV("match"),vnodetype=MV("nodetype"),vmachs=MV("machs"),vsetname=MV("setname"),
           vnode=MV("node"),vmatchstart=MV("matchstart"),v0=MV(0),v1=MV(1),vgreedy=MV("greedy"),
           vfns=MV("fns"),vcurmatch=MV("curmatch"),vlongmatch=MV("longmatch"),vscanners=MV("scanners");

///////////////////////////////////////////////////////////////
// scanner
//

class Scanner {
public:
  unsigned int masks[256],target;
  int refcount;
  int nn;
  // big 4
  Scanner () { target=0;}
  Scanner &operator = (const Scanner &r) {
     target=r.target;
     nn=r.nn;
     for (int i=0;i<256;i++) masks[i]=r.masks[i];
     return *this;
  }
  Scanner (const Scanner &r) {*this=r;}
  virtual ~Scanner(){}
  // to use in table
  int operator == (Scanner &rhs) { return this==&rhs;}
  int operator < (Scanner &rhs) { return this<&rhs;}
  Scanner(Tbl m,int inn) {
    int i,j;
    for (i=0;i<256;i++) masks[i]=~0;
    target=0;
    nn=inn;
    for (i=min(m->len()-1,31);i>=0;i--) {
       target=(target)?(target<<1):1;
       Tbl t=m->get(i,et);
       int exor=t->get(vxor,0);
       for (j=0;j<256;j++) if (t->get(j,0)^exor) masks[j]&=~target;
    }
  }
  void scan(string s, Tbl t) {
     unsigned a,i;
     for (a=~0,i=0;i<s.length();i++) {
        a<<=1; a|=masks[(int)s[i]];
        if (!(a&target)) {
           t->i(nn);
           return;
        }
     }
  }
};

typedef RCP<Scanner> Pscan;
int Hash(Pscan &s) { return Hash((int)s.rawptr());}
ostream& operator<<(ostream&os, const Pscan &v) { return os<<"Scanner("<<v->nn<<")";}

static Pscan ePs(new Scanner());
Var Mscan(Tbl t, int nn) {return MV(Pscan(new Scanner(t,nn)));}
//
// end scanner
///////////////////////////////////////////////////////////////

static Tbl newnode (Tbl nodes) {
   Tbl r;
   nodes->i(r=OP.CL);
   r->set(vnn,nodes->len()-1);
   return r;
}

static Tbl getnode(Tbl nodes, Var s) {return nodes->get(s,et);}

static Tbl newmach(Tbl nodes) {
   Tbl n=newnode(nodes);
   return OP.i(vstart,n->get(vnn)).i(vend,n->get(vnn)).i(vlongmatch,OP.CL).i(vcurmatch,OP.CL).CL;
}

static Tbl swap(Tbl in) {
   Var a=in->pop(),
       b=in->pop();
   in->i(a); in->i(b);
   return in;
}

static Tbl tos(Tbl in) {return in->get(in->len()-1,et);}

static Tbl cptbl(Tbl in, Tbl out) {
   Var k,v;
   ltForEach(k,v,in) out->set(k,v);
   return out;
}

static void dumpstate(string msg,Tbl t) {
   cout << msg;
   for (int i=0;i<t->len();i++)
     cout <<i<<": "<<t->get(i)<<"\n";
}

#define fnparm Tbl node, Tbl state, int loc, string is
typedef void (*fntype)(fnparm);
int Hash(fntype f) { return Hash((int)f);}

static void fngreedy(fnparm) {state->set(vgreedy,node->get(vgreedy));}
static void fnmatchstart(fnparm) {state->set(vmatchstart,loc);}
static void fnstarttag(fnparm) {state->set(node->get(vstarttag),loc);}
static void fnendtag(fnparm) {
          string tag=node->get(vendtag,"");
          int start=state->get(tag,0),end=loc;
          if (end<0) end=is.length();
          state->set(tag,(end>start)?is.substr(start+1,end-start):string(""));
      }
static void fnmachnum(fnparm){state->set(vmachnum,node->get(vmachnum));}
static void fnstartbacktrace(fnparm){state->set(vbts,0);}

static Tbl epmove(Tbl in, Tbl emit,int loc, string is,Tbl nodes) {
   Tbl state,node,out=OP.CL,endt=et,t;
   while (in->len()) {
      state=in->pop()->as(et);
      node=getnode(nodes,state->get(vnn));
      // execute things in this state
      if ((t=node->get(vfns,et))!=et)
         for (int i=0;i<t->len();i++) t->get(i,fngreedy)(node,state,loc,is);
      // end execute things in this state
      if (node->has(vnext))
         out->i(state);
      else if (node->has(veplist)) {
        Var nv;
        Tbl eplist=node->get(veplist,et);
        state->set(vnn,eplist->get(0));
        in->i(state);
        for (int j=1;j<eplist->len();j++) {
           Tbl ts=cptbl(state,OP.CL);
           ts->set(vnn,eplist->get(j));
           in->i(ts);
        }
      } else if (node->has(vemit)) {
        if (endt->get(vmatchstart,loc+1)>state->get(vmatchstart,0)) {
          emit->del(endt->get(vmatchstart));
          state->setsup(node->get(vemit,et));
          for (int i=0;i<emit->len();i++) state->i(emit->get(i));
          endt=emit->set(state->get(vmatchstart),state);
        }
      }
   }
   if (endt!=et) {  // have a state to emit, scoop up emitted states w/in this state and cull non greedy states
      Tbl cull=OP.CL;
      Var v;
      for (int i=endt->get(vmatchstart,0)+1;i<=loc;i++)
         if ((t=emit->get(i,et))!=et) {
            endt->i(t);
            emit->del(i);
         }
      ltForEachL(v,out) {
         state=v->as(et);
         if ((state->get(vmachnum,0)!=endt->get(vmachnum,0))
            ||(state->get(vmatchstart,0)!=endt->get(vmatchstart,0))
            ||(state->get(vgreedy,0)))
            cull->i(v);
      }
      return cull;
   }
   return out;
}


static Tbl chmove(Tbl in, Var vch,Tbl nodes) {
   Tbl state,node,out=OP.CL;
   string btn;
   while (in->len()) {
      state=in->pop()->as(et);
      node=getnode(nodes,state->get(vnn));
      if ((btn=node->get(vbacktrace,""))=="") {
         if (node->get(vxor,0)^node->get(vch,0)){
            state->set(vnn,node->get(vnext));
            out->i(state);
         }
      } else {
        string tag;
        if ((tag=state->get(btn,""))!="") {
           int sub;
           if (vch->as(0)==tag[sub=state->get(vbts,0)]) {
             sub++;
             if (sub>=(int)tag.length())
               state->set(vnn,node->get(vnext));
             else
               state->set(vbts,sub);
             out->i(state);
           }
        }
      }
   }
   return out;
}

static Tbl setfn(Tbl in, Var k, Var v, fntype f) {
   Tbl t;
   in->set(k,v);
   if ((t=in->get(vfns,et))==et) t=in->set(vfns,OP.CL);
   t->i(f);
   return in;
}

/////////////////////////////////////////////////////////////////
//
// start of methods
//
void Luthor::init() {
  nodes=OP.CL;
  err=OP.CL;
  newnode(nodes);
  getnode(nodes,v0)->set(veplist,OP.CL);
  setfn(getnode(nodes,v0),vstarttag,vmatch,fnstarttag);
  nodes->set(vscanners,OP.CL);
}

Luthor::Luthor() { init();}
Luthor::Luthor(string is, Tbl emit) { init();add(is,emit);}

Luthor::Luthor(const Luthor &in) {
  nodes=in.nodes;
  err=in.err;
}

Luthor & Luthor::operator=(const Luthor &in) {
  nodes=in.nodes;
  err=in.err;
  return *this;
}

static Tbl CM(Tbl in, int from, int to) {
  for (int i=from;i<=to;i++) in->set(i,v1);
  return in;
}


#define ANCHORSTART 512
#define ANCHOREND   513
#define NEXTCH(ch,errstr) do{if (sub>((int)is.length())) {err->i(is+" : "+errstr); return *this;}ch=is[sub++];}while (0);
#define PEEK(def) ((sub<(int)is.length())?is[sub]:(def))
Luthor &Luthor::add(string is, Tbl emit) {
   enum {PUSH,POP,MACH,CMATCH,BTRACE,FINISH,OR,SPLICE,RAWMACH,LOOP,HUH,SPLAT,PLUS,INVALID};
   int ch=0,sub=0,finished=0,mode=PUSH;
   static Tbl esc=OP.i((int)'a',CM(CM(OP.CL,'a','z'),'A','Z')).i((int)'d',CM(OP.CL,'0','9')).i((int)'s',CM(CM(OP.CL,' ',' '),9,9)).i((int)'w',CM(CM(CM(CM(OP.CL,'_','_'),'a','z'),'A','Z'),'0','9')).CL;
   Tbl tok=OP.i(OP.i(vnodetype,(int)FINISH).CL).CL;
   Tbl mach=OP.i(newmach(nodes)).CL;
   Tbl ctok,cmach;
   while (!finished) {
      if (sub==((int)is.length())) mode=POP;
      if (mode==PUSH) {
         NEXTCH(ch,"initial get ch bad");
         switch(ch) {
            case '@':
            case '(': {
                 string name="";
                 if (ch=='@') {
                    NEXTCH(ch,"unterminated @");
                    while((ch!='(')&&(ch!='@')) {
                       name.append(1,ch);
                       NEXTCH(ch,"unterminated @");
                    }
                    if (ch=='@') {
                       Tbl s=newnode(nodes),e=newnode(nodes);
                       s->i(veplist,OP.i(e->get(vnn)).CL);
                       setfn(s,vstartbacktrace,v1,fnstartbacktrace);
                       e->i(vbacktrace,name);
                       tok->i(OP.i(vnodetype,(int)BTRACE).i(vstart,s->get(vnn)).i(vend,e->get(vnn)).CL);
                       break;
                    }
                 }
                 mach->i(newmach(nodes));
                 tok->i(OP.i(vnodetype,(int)OR).i(vmachs,OP.CL).CL);
                 if (name!="") tos(tok)->set(vsetname,name);
              }break;
            case ')':
            case '|':
              mode=POP;
              break;
            case '?':
              tok->i(OP.i(vnodetype,(int)HUH).CL);
              swap(tok)->i(OP.i(vnodetype,(int)LOOP).CL);
              break;
            case '*':
              if (PEEK('$')=='?') NEXTCH(ch,"better work");
              tok->i(OP.i(vnodetype,(int)SPLAT).CL);
              swap(tok)->i(OP.i(vnodetype,(int)LOOP).i(vgreedy,(ch=='?')?v0:v1).CL);
              break;
            case '+':
              if (PEEK('$')=='?') NEXTCH(ch,"better work");
              tok->i(OP.i(vnodetype,(int)PLUS).CL);
              swap(tok)->i(OP.i(vnodetype,(int)LOOP).i(vgreedy,(ch=='?')?v0:v1).CL);
              break;
            case '[': {
                 Tbl clist=OP.CL;
                 cmach=newnode(nodes);
                 NEXTCH(ch,"unterminted [");
                 if (ch=='^') {
                   cmach->set(vxor,v1);
                   NEXTCH(ch,"unterminated [");
                 }
                 while (ch!=']') {
                   if (ch=='\\') {
                      NEXTCH(ch,"unterminated \\");
                      Tbl t=esc->get(ch,et);
                      if (t!=et) {
                         cptbl(t,cmach);
                         NEXTCH(ch,"unterminated [");
                         continue;
                      }
                   }
                   clist->i(ch);
                   if (ch!='-') cmach->set(ch,v1);
                   NEXTCH(ch,"unterminated [");
                 }
                 for (int i=1;i<(clist->len()-1);i++) {
                   if (clist->get(i,0)=='-') {
                      int s=clist->get(i-1,0),e=clist->get(i+1,0),t;
                      for (t=s;t<=e;t++) cmach->set(t,v1);
                   }
                 }
                 tok->i(OP.i(vnodetype,(int)CMATCH).i(vnode,cmach).CL);
              } break;
            case '$':
              (cmach=newnode(nodes))->set(ANCHOREND,v1);
              tok->i(OP.i(vnodetype,(int)CMATCH).i(vnode,cmach).CL);
              break;
            case '^':
              (cmach=newnode(nodes))->set(ANCHORSTART,v1);
              tok->i(OP.i(vnodetype,(int)CMATCH).i(vnode,cmach).CL);
              break;
            case '.':
              (cmach=newnode(nodes))->set(vxor,v1);
              tok->i(OP.i(vnodetype,(int)CMATCH).i(vnode,cmach).CL);
              break;
            case '\\':
              NEXTCH(ch,"unterminted backslash"); {
                 Tbl c=esc->get(ch,et);
                 if (c!=et) {
                    cmach=cptbl(c,newnode(nodes));
                    tok->i(OP.i(vnodetype,(int)CMATCH).i(vnode,cmach).CL);
                    break;
                 }
              }
            default:
              (cmach=newnode(nodes))->set(ch,v1);
              tok->i(OP.i(vnodetype,(int)CMATCH).i(vnode,cmach).CL);
              break;
         }
      } else {
         ctok=tok->pop()->as(et);
         int ntype=ctok->get(vnodetype,(int)INVALID);
         if (ntype==CMATCH) {
            Tbl n=ctok->get(vnode,et);
            if (!((n->get(ANCHORSTART,0))||(n->get(ANCHOREND,0))))
               tos(mach)->get(vcurmatch,et)->i(ctok->get(vnode));
         }else {
            cmach=tos(mach);
            if (cmach->get(vcurmatch,et)->len()>cmach->get(vlongmatch,et)->len())
               cmach->set(vlongmatch,cmach->get(vcurmatch));
            cmach->set(vcurmatch,OP.CL);
         }
         switch(ntype) {
            case OR:
               ctok->get(vmachs,et)->i(mach->pop());
               mode=PUSH;
               if (ch=='|') {
                 mach->i(newmach(nodes));
                 tok->i(ctok);
               } else {
                 Tbl start=newnode(nodes),end=newnode(nodes),t,m;
                 Var v;
                 start->set(veplist,OP.CL);
                 t=ctok->get(vmachs,et);
                 ltForEachL(v,t) {
                   m=v->as(et);
                   start->get(veplist,et)->i(m->get(vstart));
                   getnode(nodes,m->get(vend))->set(veplist,OP.i(end->get(vnn)).CL);
                 }
                 tok->i(OP.i(vnodetype,(int)RAWMACH).i(vstart,start->get(vnn)).i(vend,end->get(vnn)).CL);
                 if (ctok->has(vsetname)) {
                    //start->set(vstarttag,end->set(vendtag,ctok->get(vsetname,"")));
                    setfn(start,vstarttag,ctok->get(vsetname),fnstarttag);
                    setfn(end,vendtag,ctok->get(vsetname),fnendtag);
                 }
               } break;
            case SPLICE:
               ctok=mach->pop()->as(et);
            case RAWMACH:
               getnode(nodes,ctok->get(vend))->set(veplist,OP.i(tos(mach)->get(vstart)).CL);
               tos(mach)->set(vstart,ctok->get(vstart));
               break;
            case BTRACE: {
                 cmach=mach->pop()->as(et);
                 getnode(nodes,ctok->get(vend))->set(vnext,cmach->get(vstart));
                 cmach->set(vstart,ctok->get(vstart));
                 mach->i(cmach);
               }break;
            case CMATCH: {
                  Tbl start;
                  cmach=mach->pop()->as(et);
                  (start=ctok->get(vnode,et))->set(vnext,cmach->get(vstart));
                  cmach->set(vstart,start->get(vnn));
                  mach->i(cmach);
               }break;
            case LOOP:
               mach->i(newmach(nodes));
               if (ctok->has(vgreedy)) setfn(getnode(nodes,tos(mach)->get(vstart)),vgreedy,ctok->get(vgreedy),fngreedy);
               break;
            case HUH: {
                 cmach=mach->pop()->as(et);
                 Tbl start=newnode(nodes);
                 start->i(veplist,OP.i(cmach->get(vstart)).i(cmach->get(vend)).CL);
                 cmach->set(vstart,start->get(vnn));
                 mach->i(cmach);
                 tok->i(OP.i(vnodetype,(int)SPLICE).CL);
               } break;
            case SPLAT: {
                 cmach=mach->pop()->as(et);
                 Tbl s=newnode(nodes),e=newnode(nodes);
                 s->set(veplist,OP.i(cmach->get(vend)).CL);
                 getnode(nodes,cmach->get(vend))->set(veplist,OP.i(cmach->get(vstart)).i(e->get(vnn)).CL);
                 //mach->i(OP.i(vstart,s->get(vnn)).i(vend,e->get(vnn)).CL);  // make this use cmach
                 cmach->set(vstart,s->get(vnn));cmach->set(vend,e->get(vnn));
                 mach->i(cmach);
                 tok->i(OP.i(vnodetype,(int)SPLICE).CL);
               } break;
            case PLUS: {
                 cmach=mach->pop()->as(et);
                 Tbl end=newnode(nodes);
                 getnode(nodes,cmach->get(vend))->set(veplist,OP.i(cmach->get(vstart)).i(end->get(vnn)).CL);
                 cmach->set(vend,end->get(vnn));
                 mach->i(cmach);
                 tok->i(OP.i(vnodetype,(int)SPLICE).CL);
               } break;
            case FINISH:
               finished=1;
               break;
         }
      }
   }
   if (mach->len()>1)
      err->i(is+"unterminated '(' ?");
   else {
      Var vi;
      Tbl t=mach->get(v0,et),ne=newnode(nodes);
      getnode(nodes,v0)->get(veplist,et)->i(vi=t->get(vstart));
      setfn(getnode(nodes,vi),vmachnum,vi,fnmachnum);
      setfn(getnode(nodes,vi),vmatchstart,vi,fnmatchstart);
      setfn(getnode(nodes,vi),vgreedy,v1,fngreedy);
      getnode(nodes,t->get(vend))->set(veplist,OP.i(ne->get(vnn)).CL);
      setfn(ne,vendtag,vmatch,fnendtag);
      ne->set(vemit,emit);
      nodes->get(vscanners,et)->i(Mscan(t->get(vlongmatch,et),vi->as(0)));
      //cout <<"expression="<<is<<"\n";
      //dumpstate("nodes\n",nodes);
   }
   return *this;
}

static Tbl startstate() { return OP.i(vnn,0).CL;}

Tbl Luthor::find(string s) {
   Tbl emit=OP.CL,states=OP.i(startstate()).CL,ret=OP.CL,t,eplist=OP.CL;
   string tmp;
   t=nodes->get(vscanners,et);
   for (int i=0;i<t->len();i++) t->get(i,ePs)->scan(s,eplist);
   if (!eplist->len()) return ret;
   getnode(nodes,v0)->set(veplist,eplist);
   states=epmove(states,emit,-1,s,nodes);
   states=chmove(states,MV(ANCHORSTART),nodes);
   states->i(startstate());
   states=epmove(states,emit,-1,s,nodes);
   for (int i=0;i<=(int)s.length();i++) {
      //tmp=s;tmp[i]='$'; cout << "\n\n"<<tmp<<"\n";
      states=chmove(states,(i==(int)s.length())?MV(ANCHOREND):MV((int)s[i]),nodes);
      //dumpstate("chmove\n",states);
      states->i(startstate());
      states=epmove(states,emit,i,s,nodes);
      //dumpstate("epmove\n",states);
   }
   Var v;
   t=emit->keys();
   ltForEachL(v,t) ret->i(emit->get(v));
   return ret;
}
} // end namespace
